'''
归并排序:将两个的有序数列合并成一个有序数列，我们称之为"归并"。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。
1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果

2. 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

复杂度:
稳定性:稳定
'''


def merge_sort(list):
    length = len(list)
    if length < 2:
        return list
    mid = length // 2
    l_list = merge_sort(list[:mid])
    r_list = merge_sort(list[mid:])
    return merge(l_list, r_list)


def merge(l_list, r_list):
    l_idx, r_idx = 0, 0
    result = []
    while l_idx < len(l_list) and r_idx < len(r_list):
        if l_list[l_idx] < r_list[r_idx]:
            result.append(l_list[l_idx])
            l_idx += 1
        else:
            result.append(r_list[r_idx])
            r_idx += 1
    result += l_list[l_idx:]
    result += r_list[r_idx:]
    return result


if __name__ == '__main__':
    li = [31, 65, 12, 98, 54, 21, 100, 4]
    result = merge_sort(li)
    print(result)
